1. Field of the Invention
The present invention relates to a Viterbi decoder, and more particularly, to a super high speed Viterbi decoder and a decoding method using a circularly connected 2-dimensional analog processing cell array, which implement analog signal processing cells performing functions of nodes in a trellis diagram of the Viterbi decoder, have a 2-dimensional analog parallel processing structure, and have a circularly connected structure by connecting the output column cells with the decoding column cells in the 2-dimensional analog cell array, thereby not requiring any path memories and performing decoding at a super high speed.
2. Background of the Related Art
In high-speed data communication or high-density magnetic recoding media, the signals are easily distorted or contaminated by noise. Recovering the original data from the distorted or noisy signals is necessary. A Viterbi decoder is the one devised for such purpose, which decodes a convolution code using an optimization method.
The decoder is a simple model of a dynamic programming, which possesses excellent data correction efficiency by utilizing an optimal path obtained on the trellis diagram with code-symbol differences.
The Viterbi decoder accumulates the code-symbol difference (hereinafter, referred to as “code-symbol error”) between a set of input code symbols and a set of reference code symbols assigned at branches of a trellis diagram shown in FIG. 1, searches for an optimum path which has minimum code-symbol error, and performs decoding depending on the position of the branch through which the optimum path passes. For example, in FIG. 1, if the optimum path which has the minimum value of the accumulated error passes a branch corresponding to a solid line of the trellis diagram, the decoder decodes to logic 0, but if the optimum path passes a dotted line, the decoder decodes to logic 1. With such algorithm of the Viterbi decoder, received code symbols could be corrected even though they are distorted or contaminated by noise in the communication system.
The Viterbi decoder obtains a globally optimal path via the calculation of the following [Expression 1] at each local node.Di,j=min{Dk,l+dij,kl, (k,l)εS}  [Expression 1]where Dk,l is the shortest total distance from a cell (k, l) to its destination, dij,kl is a local distance between a cell (i, j) and a cell (k, l). In the application of the Viterbi decoder, the local distance is assigned with the code-symbol error between a set of received code symbols and the one assigned on each branch of the trellis diagram. In addition, in the [Expression 1], S is a set of the cells in the vicinity of the cell (i,j), and min is a function for outputting the minimum value of enumerated items The processing of [Expression 1] is done at each node of the trellis diagram of the Viterbi decoder. For the decoding, each node of the trellis diagram accumulates the minimum value of the code symbol error at each branch with [Expression 1] onto the one transmitted from the former nodes.
In most of conventional Viterbi decoder chips, all nodes of the trellis diagram are not implemented with hardware circuits, but only the nodes of one column are implemented. During each processing stage, outputs of all nodes are stored in path memories for searching of the optimum path. FIG. 2a is a circuit diagram of a conventional digital decoder. The conventional digital Viterbi decoder shown in FIG. 2a requires an analog-digital converter which consumes lots of power. Also, the decoding speed is low due to the processing requirement of the multiple steps for determining the optimal path on the path memory.
To overcome such problem in the digital Viterbi decoder, a method using analog circuits for Viterbi decoder has been disclosed as shown in FIG. 2b. The power consumption in such analog Viterbi decoder is reduced and the decoding speed is improved significantly. However, the conventional analog Viterbi decoder still requires the digital path memories as included in the digital Viterbi decoder. Furthermore, it still has a speed limitation due to the back-tracking process for finding an optimum path on the path memories. IEEE Trans. Inform. Theory, vol. IT-13, pp-260–269, April 1967 disclose “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm” written by A. J. Viterbi. IEEE Trans. Inform. Theory, vol. IT-18, pp. 363–378. y 1972 disclose “Maximum-likelihood sequence estimation of digital sequences in the presences of intersymbol interference” written by G. D. Forney, Jr. IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, pp. 1527–1537, vol. 45, no. 12, December 1998 disclose “BiCMOS circuits for analog Viterbi decoders” written by M. H. Shakiba, D. A. Johns, K. W. Martin. IEEE Journal of Selected areas in Communications, vol. 10, no. 1, January 1992 disclose “Simulated performance of analog Viterbi detectors” written by R. R. Spencer.